https://leetcode-cn.com/problems/employee-importance/submissions/
public class Solution {
    /*
     * 员工重要性问题
     * HashMap搜索快
     *
     *
     * */

    class Employee {
        public int id;
        public int importance;
        public List<Integer> subordinates;
    }

    ;

    public int DFSImportance(Map<Integer, Employee> map, int id) {
        Employee e = map.get(id);
        int sum = e.importance;
        for (int sub : e.subordinates) {
            sum += DFSImportance(map, sub);
        }
        return sum;
    }

    public int getImportance(List<Employee> employees, int id) {
        HashMap<Integer, Employee> map = new HashMap<>();
        for (Employee e : employees) {
            map.put(e.id, e);
        }
        return DFSImportance(map, id);
    }


    /*
     * 用List解
     *
     * */
    public int DFSImpertance(List<Employee> employees, List<Integer> list) {
        int sum = 0;
        if (list == null) {
            return 0;
        }
        for (int id : list) {
            for (Employee employee : employees) {
                if (employee.id == id) {
                    sum += employee.importance;
                    list = employee.subordinates;
                    sum += DFSImpertance(employees, list);
                }
            }
        }
        return sum;
    }

    public int getImportance2(List<Employee> employees, int id) {
        int sum = 0;
        List<Integer> list = new ArrayList<>();
        for (Employee employee : employees) {
            if (employee.id == id) {
                sum = employee.importance;
                list = employee.subordinates;
            }
        }
        return sum + DFSImpertance(employees, list);
    }

    /*
     * List优化
     *
     * */
    public int DFSImpertance2(List<Employee> employees, int id) {
        int sum = 0;
        for (Employee employee : employees) {
            if (employee.id == id) {
                sum += employee.importance;
                for (int idchild : employee.subordinates) {
                    sum += DFSImpertance2(employees, idchild);
                }
            }
        }
        return sum;
    }

    public int getImportance3(List<Employee> employees, int id) {
        return DFSImpertance2(employees, id);
    }
}